package a00_LeetCode.LinkedList;

/**
 * @Author quan
 * @Description 反转链表：输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
 * @Date 2023/3/25 20:23
 */
public class Num206_ReverseList {
    /*public ListNode reverseList(ListNode head) {
        *//**
         * 方法1：头插法：先产生一个虚拟头接节点，从head开始不断遍历原链表，每遍历到一个节点，就产生一个与该值相等的新节点，
         * 将该新节点不断头插到虚拟头结点后，最终dummyHead.next就是反转后链表的头结点
         *//*
        //边界条件：
        if (head == null || head.next == null) {
            return head;
        }
        //产生虚拟头节点
        ListNode dummyHead = new ListNode();
        //遍历原链表，不断产生新节点，将该新节点不断头插到虚拟头结点之后
        while (head != null) {
            ListNode newNode = new ListNode(head.val);
            newNode.next = dummyHead.next;//将新节点与原先的节点相连接
            dummyHead.next = newNode;//将新节点头插到虚拟头结点后
            head = head.next;
        }
        return dummyHead.next;
    }*/
    /**
     * 方法2：在原链表上移动
     */
   /* public ListNode reverseList(ListNode head) {
        //边界条件
        if (head == null || head.next == null) {
            return head;
        }
        //让第一个指针指向空，第二个指针指向链表的头，当第二个指针为空的时候结束遍历
        ListNode prev = null;
        ListNode cur = head;
        while (cur!=null){
            //保存第二个指针的下一个指向（因为要对第二个指针进行操作，防止后面的值丢失。）
            ListNode temp = cur.next;
            cur.next = prev;//让第二个指针指向第一个指针
            //移动两个指针的位置
            prev = cur;
            cur = temp;
        }
        //最终第一个指针指向的值就是头结点
        return prev;
    }
*/
    /**
     * 方法3：递归法
     */
    /*public ListNode reverseList(ListNode head) {
        //边界条件
        if (head == null || head.next == null) {
            return head;
        }
        //处理头节点之后的子链表：进行反转
        ListNode next = head.next;
        ListNode newHead = reverseList(head.next);
        //拼接当前头结点和转后的子链表
        head.next = null;//先断开原先链表头结点之后的节点
        next.next = head;//连接反转后链表的尾部与原先链表的头部
        return newHead;
    }*/
    /**
     * 双指针思想的递归：与方法2的思想一致。方法2用的循环，这里用的递归。
     */
    public ListNode reverseList(ListNode head) {
        return reverse(null,head);
    }

    private ListNode reverse(ListNode prev, ListNode cur) {
        if(cur == null){
            return prev;
        }
        ListNode temp = cur.next;
        cur.next = prev;
        //递归的反转子链表
        return reverse(cur, temp);
    }
}
